{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Network Analysis with NetworkX\n",
    "\n",
    "*by Georgy Lazarev*   **(mlcourse slack: jorgy)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Systems are ubiquitous these days in various fields of science, industry and daily-life situations. Majority of them (to name few, social interactions, telephone and transport networks) can be represented as networks or graphs (sets of nodes and edges where nodes characterize certain objects and edges indicate some kind of connection between them) and therefore are suitable for analysis. \n",
    "\n",
    "We might want to analyze relationships between participants or actor in those systems to get some valuable insights:\n",
    "\n",
    "- Which nodes are more important (influencers in network)\n",
    "- Pathfinding – determining shortest paths between certain nodes\n",
    "- Structure - finding cliques, community detection (we'll discuss those terms later)\n",
    "\n",
    "In this tutorial I'll introduce you to the NetworkX - Python package for 'the creation, manipulation, and study of the structure, dynamics, and functions of complex networks'. Important properties pointed out by developers:\n",
    " - provides an interface to existing numerical algorithms and code written in C, C++, and FORTRAN, thus resulting in promising speed perfomance \n",
    " - the ability to painlessly work with large nonstandard data sets.\n",
    " \n",
    "Let's start with some basic things. At first you need to install NetworkX (*'pip install networkx'* or *'conda install ..'* if you are working under Anaconda)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing necessary packages\n",
    "import csv\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "\n",
    "%matplotlib inline\n",
    "import warnings\n",
    "from collections import defaultdict\n",
    "\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# creating empty Graph\n",
    "G = nx.Graph()\n",
    "\n",
    "# you can now add nodes and edges\n",
    "G.add_node(\"a\")\n",
    "G.add_node(1)\n",
    "G.add_edge(\"a\", 1)\n",
    "# or creating list of nodes/edges in advance\n",
    "G.add_nodes_from([2, 3, 4])\n",
    "G.add_edges_from([(2, 4), (\"a\", 3)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# setting attribute while creating node\n",
    "G.add_node(\"John\", age=26)\n",
    "\n",
    "# setting attribute to already existing node\n",
    "G.node[\"John\"][\"hobby\"] = \"writing music\"\n",
    "nx.set_node_attributes(G, \"number\", 7)\n",
    "\n",
    "# graph with random weghts\n",
    "weights = {}\n",
    "for e in G.edges():\n",
    "    G[e[0]][e[1]][\"weight\"] = np.random.random()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(G.edges())\n",
    "print(G.edges(data=True))\n",
    "# data=True prints attributes too"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display(type(G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(nx.info(G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G, with_labels=True, node_size=900)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's probably worth mentioning that calling .draw without specifying *pos* argument will result in different layouts of nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis of real graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Here](http://konect.uni-koblenz.de/networks/) you can find real networks stored as graph representations (edgelist mostly) in .tsv format. For simplicity I picked \n",
    "quite small undirected [graph](https://www.dropbox.com/s/4n86gethjw98gqk/out.dolphins?dl=0), which represent frequent social interactions between 62 dolphins from community living off Doubtful Sound,\n",
    "a fjord in New Zealand. So this is sort of social network.\n",
    "\n",
    "Reading graphs from files doesn't have unified way as data can be stored in different formats and graphs can be represented differently (adjacency matrix, edge lists, adjacency list). I'd recommend you go for reference [here](https://networkx.github.io/documentation/networkx-1.10/reference/convert.html) and [here](https://networkx.github.io/documentation/stable/reference/readwrite/index.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = []\n",
    "with open(\"datasets/out.dolphins\", \"r\") as f:\n",
    "    filereader = csv.reader(f, delimiter=\"\\t\", quotechar='\"')\n",
    "    next(filereader)  # we'll skip header row\n",
    "    for row in filereader:\n",
    "        edges.append(row[:2])\n",
    "edges[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# now create graph from edgelist we made in previous step\n",
    "GD = nx.from_edgelist(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(nx.info(GD))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are other types of vizualization except usual one (especially useful when you are dealing with large graphs) - ArcPlot, MatrixPlot and etc. I'll show only one  here - CircosPlot\n",
    "Let's install and import nice visualization package for NetworkX - [nxviz](https://github.com/ericmjl/nxviz). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nxviz as nv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = nv.CircosPlot(GD, node_labels=True)\n",
    "c.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was fast :-) Now let's dive into analysis of our dolphins social graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# .has_edge method allows us to check presence of direct interaction between two nodes\n",
    "\n",
    "GD.has_edge(\"40\", \"37\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\n",
    "    \"shortest path from node 12 to 5 is of length\",\n",
    "    nx.shortest_path_length(GD, \"12\", \"5\"),\n",
    "    \":\",\n",
    "    nx.shortest_path(GD, \"12\", \"5\"),\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For every vertex in graph we can calculate its degree – number of adjacent (connected by an edge )vertices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display(list(GD.neighbors(\"9\")))\n",
    "print(\"node 9 has %d neighbors\" % GD.degree()[\"9\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GD.degree()\n",
    "# returns dictionary with all nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find 5 nodes with largest amount of neighbors\n",
    "sorted(dict(GD.degree()).items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That brings us to several types of centrality - metric for describing importance of a node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Degree centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ degree   \\  centrality = \\frac {degree\\ of\\ node} {number\\ of \\ nodes\\ in \\ network} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We create dictionary with nodes and their degree centralities\n",
    "degcent = nx.degree_centrality(GD)  # for getting dictionary with nodes and\n",
    "# their degree centralities as keys and values respectively\n",
    "\n",
    "print(\"Networkx degree centrality for node 16:\", degcent[\"16\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see 5 nodes with largest degree centrality:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(degcent.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we'll store node with the largest degree centraliy as 'nld '\n",
    "nld = sorted(degcent.items(), key=lambda x: x[1], reverse=True)[:1][0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here goes sort of vizualization of this node:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "palette = sns.color_palette(\"coolwarm\", 2).as_hex()\n",
    "palette"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this list wi'll be used in .draw call.\n",
    "node_colors = [palette[0] if n != nld else palette[1] for n in GD.nodes()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned above you can set attributes to nodes. Let's say we want each node to keep its degree as (one of) attribute:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in GD.nodes():\n",
    "    GD.node[n][\"degree centrality\"] = degcent[n]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use it in customizing our vizualization:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = nv.CircosPlot(GD, node_order=\"degree centrality\", node_labels=True)\n",
    "c.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Closeness centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$closeness   \\  centrality = \\frac {N\\ -\\ 1} {sum\\ of \\ distances\\ to \\ each \\ node \\ from \\ current \\ one}$$\n",
    "\n",
    "where $N = $ number of nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compares how many steps (edges) it would take to reach every other node in a network (using shortest paths obviously).\n",
    "Intuitively you can think of this as of 'average distance' to all other nodes.\n",
    "\n",
    "Degree centrality takes into account only direct connections thus deluding analyst sometimes as current node can be central only in local neighborhood. That's why closeness centrality is important.\n",
    "\n",
    "In case pf being not fully connected, this algorithm computes the closeness centrality for each connected component separately.\n",
    "By the way, you can see connected parts of your graph this way (in our case graph is itself connected):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for comp in nx.connected_components(GD):\n",
    "    print(comp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculating closeness centrality for each node\n",
    "clocent = nx.closeness_centrality(GD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(clocent.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in GD.nodes():\n",
    "    GD.node[n][\"closeness centrality\"] = clocent[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nlcc = sorted(clocent.items(), key=lambda x: x[1], reverse=True)[:1][0][0]\n",
    "palette = sns.color_palette(\"coolwarm\", 2).as_hex()\n",
    "node_colors = [palette[0] if n != nlcc else palette[1] for n in GD.nodes()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Betweeness Centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can calculate shortest path for each pair of node (if they belong to one connected component obviously).\n",
    "So betweeness centrality of a node indicates to how often this current node becomes a part of all shortest paths."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$betweeness   \\  centrality = \\frac {number \\ of \\ shortest \\ paths \\ passing \\ throught \\ current \\ node } {totul \\ number \\ of \\ shortest \\ paths}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intuitively betweeness centrality can be thought of as measure of node influence in network. For example, members of a group with 'big' influence can be useful in terms of spreading a message/information. As an other example - in telecommunication network a node with largest betweeness centrality has biggest control due to amount information transferring through it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "betcent = nx.betweenness_centrality(GD)\n",
    "for n in GD.nodes():\n",
    "    GD.node[n][\"betweeness centrality\"] = betcent[n]\n",
    "\n",
    "sorted(betcent.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nlbc = sorted(clocent.items(), key=lambda x: x[1], reverse=True)[:1][0][0]\n",
    "palette = sns.color_palette(\"coolwarm\", 2).as_hex()\n",
    "node_colors = [palette[0] if n != nlbc else palette[1] for n in GD.nodes()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$Betweeness \\ centrality \\ for \\ edges$\n",
    "\n",
    "I guess, this term doesn't need an explanation as its meaning is almost the same as for node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "betcent_e = nx.edge_betweenness_centrality(GD)\n",
    "sorted(betcent_e.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for e in GD.edges():\n",
    "    GD[e[0]][e[1]][\"betweeness centrality\"] = betcent_e[e]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the bigger is betweeness centrality - the darker are edges\n",
    "c = nv.CircosPlot(GD, edge_color=\"betweeness centrality\")\n",
    "c.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "elbc = sorted(betcent_e.items(), key=lambda x: x[1], reverse=True)[:1][0][0]\n",
    "palette = [\"#bd3c14\", \"#009688\"]\n",
    "edge_colors = [palette[0] if e != elbc else palette[1] for e in GD.edges()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, edge_color=edge_colors, with_labels=True, node_color=\"#999999\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The green edge is the one with the largest betweeness centrality. Colors are quite distinguishable, I hope :-)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eigenvector Centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, I tried to avoid this but here is real formula without words:\n",
    "\n",
    "$$ Ax = \\lambda x $$\n",
    "\n",
    "A is adjacency matrix of graph, (one of the (if not the one) most-used representation of graph) - NxN matrix where values in intersections of columns and rows corresponds to connection between respective nodes. Non-zero values stand for connection between nodes (in case of unweighted graph 1 is the only option) and zero does mean nodes are not directly connected.\n",
    "$ \\lambda $ is egenvalue of A and  the largest eigenvalue associated with the eigenvector of the adjacency matrix A \n",
    "\n",
    "Importance of a node depends on the importance of its neighbors. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eigcent = nx.eigenvector_centrality_numpy(GD)\n",
    "sorted(eigcent.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in GD.nodes():\n",
    "    GD.node[n][\"eigenvector centrality\"] = eigcent[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# you can use this function for colouring nodes according to their values of given attribute\n",
    "def attribute_color(G, attribute):\n",
    "    attrs = [G.node[n][attribute] for n in G.nodes()]\n",
    "    uattrs = sorted(list(set(attrs)))\n",
    "    palette = sns.color_palette(\"Blues\", len(uattrs)).as_hex()\n",
    "    colmap = dict(zip(uattrs, palette))\n",
    "    node_colors = [colmap[at] for at in attrs]\n",
    "    nx.draw(G, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see all four types of centrality in one picture. Darker shades of blue corresponds to bigger values of metric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(12, 12))\n",
    "\n",
    "plt.subplot(221)\n",
    "attribute_color(GD, \"degree centrality\")\n",
    "plt.subplot(222)\n",
    "attribute_color(GD, \"closeness centrality\")\n",
    "plt.subplot(223)\n",
    "attribute_color(GD, \"betweeness centrality\")\n",
    "plt.subplot(224)\n",
    "attribute_color(GD, \"eigenvector centrality\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Link Prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have infromation about social network at this given moment we might want to try to predict which new interaction are more likely to happen in future.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard coefficient\n",
    "\n",
    "To find pair of nodes which are 'similar' to each other we can use the Jaccard coefficient \n",
    "It measures what proportion of neighbors a pair of nodes share."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$Jaccard _{uv}  = \\frac { |N_u \\cap N_v |} {|N_u\\ \\cup \\ N_v|}$$\n",
    "\n",
    "where $N_u$ - set of neighbors of node $u$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "jc = nx.jaccard_coefficient(GD)\n",
    "jcd = {}\n",
    "for u, v, p in jc:\n",
    "    jcd[(u, v)] = p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(jcd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How much pair of nodes have a probablity higher than 0.5 to connect in nearest future?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len([(u, v) for u, v in jcd.keys() if jcd[(u, v)] > 0.5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's see those pairs\n",
    "[(u, v) for u, v in jcd.keys() if jcd[(u, v)] > 0.5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's vizualize nodes that are most likely to interact the same way as with nodes before\n",
    "ejc = sorted(jcd.items(), key=lambda x: x[1], reverse=True)[:1][0][0]\n",
    "palette = sns.color_palette(\"coolwarm\", 2).as_hex()\n",
    "node_colors = [palette[0] if n not in ejc else palette[1] for n in GD.nodes()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Preferential Attachment\n",
    "\n",
    "In the other approach to link prediction nodes with high degree will be the ones to be more likely to get future connections. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "PA _{uv}  = { |N_u \\cap N_v |} \\ or \\ {deg_u * deg_v}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pa = nx.preferential_attachment(GD)\n",
    "pad = {}\n",
    "for u, v, p in pa:\n",
    "    pad[(u, v)] = p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(pad.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can scale it though :-)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "epa = sorted(pad.items(), key=lambda x: x[1], reverse=True)[:1][0][0]\n",
    "palette = sns.color_palette(\"coolwarm\", 2).as_hex()\n",
    "node_colors = [palette[0] if n not in epa else palette[1] for n in GD.nodes()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resource Allocation\n",
    "\n",
    "$$RA _{uv}  =  \\sum_{w\\in N_u \\cap N_v} { \\frac { 1} {deg_w } }$$\n",
    "\n",
    "Inspiration for proposing this similarity measure is following: we consider two nodes $u$ and $v$, where $u$ can allocate resources to $v$ (as well as the other way around), through their common neighbors (transmitters). We assume that each node has one resource only which it assigns to its neighbors evenly. Thus the expression above is used for calculating amount of resources node can get from the other one. \n",
    "There is one very similar method proposed for measuring probability of interaction - *Adamic/Adar (AA)*. The difference is that the latter one has logarithm in denominator. So RA penalizes high-degree neigbours more.\n",
    "\n",
    "[Here](https://networkx.github.io/documentation/stable/reference/algorithms/link_prediction.html) you can find all implemented similarity indexes in NetworkX."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ra = nx.resource_allocation_index(GD)\n",
    "rad = {}\n",
    "for u, v, p in ra:\n",
    "    rad[(u, v)] = p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(rad.items(), key=lambda x: x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "era = sorted(rad.items(), key=lambda x: x[1], reverse=True)[:1][0][0]\n",
    "palette = sns.color_palette(\"coolwarm\", 2).as_hex()\n",
    "node_colors = [palette[0] if n not in era else palette[1] for n in GD.nodes()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD, node_color=node_colors, with_labels=True, node_size=200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structure analysis\n",
    "\n",
    "### Cliques\n",
    "\n",
    "Cliques in network analysis - completely connected graphs (or subset of nodes). Maximal cliques is such cliques that stop being cliques with addition of any single edge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(list(nx.find_cliques(GD)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(nx.find_cliques(GD))[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, edge is also under a definition of clique.\n",
    "And just so you knew  this algorithm is not suitable for directed graph (as [documentation](https://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.clique.find_cliques.html) states)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from networkx.algorithms.community import k_clique_communities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*k_clique_communities* return a list of groups, each produced by combining all k-size cliques sharing $k-1$ nodes. This represents the concept of *clique percolation method* that allows for discovering overlapping structure of network by detecting fully-connected subgraphs of $k$ nodes. Two $k$ - cliques are considered adjacent if they share $k$ neighbours."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(k_clique_communities(GD, 3, cliques=None))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Community Detection\n",
    "\n",
    "Different groups of nodes seem to be more densely connected internally rather than externally, which makes them called “communities”. In the past decade the problem of graph partitioning into number of groups attracted a lot of interest from physics and statisticians. This field of study, commonly called ‘community detection’, now includes growing number of papers suggesting new algorithms and methods and modifications of existing ones. The importance of community detection is quite obvious as it allows for analyzing the structure of networks, to make visualization more clear, to make certain conclusions or predictions based on analysis. To note, before detection a number of communities is uncertain, which makes the difference between community detection and clustering, where an amount of clusters is given intentionally. Moreover, communities can differ by size and density, can incorporate hierarchical structure. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, networkX package for community detection has an algorithm based on [this paper](https://arxiv.org/pdf/cond-mat/0112110.pdf)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from networkx.algorithms.community import girvan_newman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea of Girvan Newmann algorithm is that at each step edges with highest betweeness are removed thus separating graph into densely connected parts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gn = girvan_newman(GD)\n",
    "# returns an iterator over tuples of communities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So each tuple is a partition of a graph at current level of algorithm. At the last iteration all nodes themselves are communities:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(list(gn)[-1])\n",
    "# as you might remember there are 62 nodes in our network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see a state of partition at the second iteration:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gn = girvan_newman(GD)\n",
    "next(gn)\n",
    "second_iteration = tuple(sorted(c) for c in next(gn))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(second_iteration)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from seaborn import color_palette"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this function you can make coloured vizualization of communities:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def colour_communities(G, partition):\n",
    "    commap = {}\n",
    "    for n in G.nodes():\n",
    "        for i, c in enumerate(partition):\n",
    "            if n in c:\n",
    "                commap[n] = i\n",
    "                G.node[n][\"community\"] = i\n",
    "    cs = [G.node[n][\"community\"] for n in G.nodes()]\n",
    "    ucs = list(set(cs))\n",
    "    palette = color_palette(\"coolwarm\", len(ucs)).as_hex()\n",
    "    colmap = dict(zip(ucs, palette))\n",
    "    node_colors = [colmap[c] for c in cs]\n",
    "\n",
    "    return node_colors, colmap, palette"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# store partitions at first four iterations\n",
    "gn = girvan_newman(GD)\n",
    "first_iteration = tuple(sorted(c) for c in next(gn))\n",
    "second_iteration = tuple(sorted(c) for c in next(gn))\n",
    "third_iteration = tuple(sorted(c) for c in next(gn))\n",
    "fourth_iteration = tuple(sorted(c) for c in next(gn))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[len(part) for part in list(first_iteration)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First iteration - two communities consisting of 41 and 21 nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display([len(part) for part in list(second_iteration)])\n",
    "display([len(part) for part in list(third_iteration)])\n",
    "display([len(part) for part in list(fourth_iteration)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now pictures!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(20, 15))\n",
    "\n",
    "\n",
    "plt.subplot(221)\n",
    "node_colors, color_map, palette = colour_communities(GD, first_iteration)\n",
    "nx.draw(GD, node_color=node_colors, with_labels=True)\n",
    "plt.subplot(222)\n",
    "node_colors, color_map, palette = colour_communities(GD, second_iteration)\n",
    "nx.draw(GD, node_color=node_colors, with_labels=True)\n",
    "plt.subplot(223)\n",
    "node_colors, color_map, palette = colour_communities(GD, third_iteration)\n",
    "nx.draw(GD, node_color=node_colors, with_labels=True)\n",
    "plt.subplot(224)\n",
    "node_colors, color_map, palette = colour_communities(GD, fourth_iteration)\n",
    "nx.draw(GD, node_color=node_colors, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subgraph\n",
    "\n",
    "When you have a large graph but want to vizualize or analyze only a small portion of it it can be helpful to extract nodes of interest and corresponding edges. Thats what subgraph is about.\n",
    "\n",
    "For example, let's construct a subgraph based on node with the largest degree and its neigbours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(dict(GD.degree()).items(), key=lambda x: x[1], reverse=True)[:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nbrs = list(GD.neighbors(\"15\"))\n",
    "nbrs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# don't forget to include your node of interest\n",
    "nbrs.append(\"15\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GD_sub15 = GD.subgraph(nbrs)\n",
    "print(nx.info(GD_sub15))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(GD_sub15, with_labels=True, alpha=0.7, node_size=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bipartite graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bipartite graphs - graphs such that:\n",
    " - partitioned into two sets (each node belong to one of the two groups)\n",
    " - node can be connected only to node from other set\n",
    " \n",
    " \n",
    " As an example of bipartite graph you can imagine a graph consisting of two sets: customers and products they purchase, website users and movies they leave reviews to."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In networkX bipartite concept can be implemented by keyword *bipartite* when specifying metadata for nodes (or by any attribute name you want)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I took [graph](https://www.dropbox.com/s/mnxzbndbxq1dif5/out.brunson_club-membership_club-membership?dl=0) from the [same source](http://konect.uni-koblenz.de/networks/). It's also real but still toy (in a way) example. Network consists of 40 nodes - 25 corporate executive officers and 15 social organizations they are members of. And each edge (in the amount of 95) tells that current person has a membership status in corresponding club."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = []\n",
    "with open(\"datasets/out.brunson_club-membership_club-membership\", \"r\") as f:\n",
    "    filereader = csv.reader(f, delimiter=\" \", quotechar='\"')\n",
    "    next(filereader)  # skips header row\n",
    "    next(filereader)\n",
    "    for row in filereader:\n",
    "        edges.append(row[:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# in original format each set of nodes begins from 1.. so for the sake of distinguishability this is what I came to\n",
    "for edge in edges:\n",
    "    edge[0] = \"m\" + edge[0]\n",
    "    edge[1] = \"c\" + edge[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CM = nx.Graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clubs = [\"c\" + str(i + 1) for i in range(15)]\n",
    "members = [\"m\" + str(i + 1) for i in range(25)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CM.add_nodes_from(clubs, bipartite=\"clubs\")\n",
    "CM.add_nodes_from(members, bipartite=\"members\")\n",
    "CM.add_edges_from(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top = nx.bipartite.sets(CM)[0]\n",
    "pos = nx.bipartite_layout(CM, top, scale=7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(nx.info(CM))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bipartite graphs can be visualized the following way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(7, 7))\n",
    "nx.draw(\n",
    "    CM,\n",
    "    pos,\n",
    "    node_color=\"#9699bc\",\n",
    "    alpha=0.7,\n",
    "    with_labels=True,\n",
    "    aspect_ratio=0.1,\n",
    "    node_size=450,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now it'a time to show application (kind of) of biparite graph - recommendations. As well as graph our task will be relatively toy. Let's try to recommend to person a organization to join based on similar persons. (similarity between persons is measured based on organization they have membership of."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# function that produces the set of clubs both persons are going to\n",
    "def shared_partition(G, mbr1, mbr2):\n",
    "    nbrs1 = G.neighbors(mbr1)\n",
    "    nbrs2 = G.neighbors(mbr2)\n",
    "    overlap = set(nbrs1).intersection(nbrs2)\n",
    "    return overlap\n",
    "\n",
    "\n",
    "def member_similarity(G, mbr1, mbr2):\n",
    "    shared_nodes = shared_partition(G, mbr1, mbr2)\n",
    "    return len(shared_nodes) / len(clubs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "shared_partition(CM, \"m3\", \"m5\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "member_similarity(CM, \"m23\", \"m13\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def most_similar_members(G, member, thr=0.14):  # you can specify the threshold\n",
    "    mbrs = members.copy()\n",
    "    mbrs.remove(member)\n",
    "    similarities = defaultdict(list)\n",
    "    for m in mbrs:\n",
    "        similarity = member_similarity(G, member, m)\n",
    "        similarities[similarity].append(m)\n",
    "\n",
    "    max_similarity = max(similarities.keys())\n",
    "    if max_similarity >= thr:\n",
    "        return [similarities[max_similarity]]\n",
    "    else:\n",
    "        return [[]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "most_similar_members(CM, \"m15\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recommend_club(G, member, thr=0.14):\n",
    "    smlr = most_similar_members(G, member, thr)\n",
    "    tmp = [\n",
    "        list(G.neighbors(n)) for n in smlr[0]\n",
    "    ]  # we make a list of neighbours lists for every node in list of similar members\n",
    "    smlr_clubs = set([i for sub in tmp for i in sub])  # ..and then flatten it\n",
    "    mbr_clubs = set(G.neighbors(member))\n",
    "    return list(smlr_clubs.difference(mbr_clubs))\n",
    "\n",
    "\n",
    "print(recommend_club(CM, \"m15\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# store recommendations for every member\n",
    "recommendations = {}\n",
    "for mbr in members:\n",
    "    recommendations[mbr] = [recommend_club(CM, mbr)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "recommendations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As I said, it is a very toy example, that's why default threshold (0.14) is so small. But I guess, you've grasphed an idea of what can be done. Also there are several papers dedicated to link prediction in bipartite graphs but that's already beyond the scope of this tutorial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's all :-) I hope you've learned something new from this. \n",
    "NetworkX is a set of various tools for study of the network structure and dynamics which you can use for your needs to find useful insight in your data. Network analysis,in turn, is quite an useful approach to analyze systems and can be implemented in biology, social science, logistics. Moreover, community detection has been there for less than 20 years and new algorithms/methods are proposed nowadays. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here you can find something useful:\n",
    "\n",
    " - [course in DataCamp](https://www.datacamp.com/courses/network-analysis-in-python-part-1)\n",
    " - [video of presentation at PyData Carolinas 2016](https://www.youtube.com/watch?v=7fsreJMy_pI)\n",
    " - [NetworkX documentation](https://networkx.github.io/documentation/stable/reference/index.html)\n",
    " - [the very first paper dedicated to *community detection* I believe](https://arxiv.org/pdf/cond-mat/0112110.pdf)\n",
    " - [another one about community detection but monography](https://arxiv.org/pdf/0906.0612.pdf)\n",
    " - [collection of networks, once again](http://konect.uni-koblenz.de/networks/)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
